package com.dmall.sort.algorithm;

/**
 * 希尔排序算法
 * 希尔排序是插入排序的一种改良版本
 *
 * @author xiao1.wang
 * @date 2021/10/10 16:06
 */
@SuppressWarnings("all")
public class ShellSort implements Sort {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        shellSort(arr, arr.length);
    }

    private void shellSort(int[] arr, int n) {
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap; j < n; j += gap) {
                    int value = arr[j];
                    int k = j - gap;
                    for (; k >= 0; k -= gap) {
                        if (arr[k] > value) {
                            arr[k + gap] = arr[k];
                        } else {
                            break;
                        }
                    }
                    arr[k + gap] = value;
                }
            }
        }
    }

    @Override
    public String getName() {
        return "希尔排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new ShellSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
